// :sqlist.h
#include <stdlib.h>

const int LIST_INIT_SIZE=100;
const int LISTINCREMENT=10;

template <class ElemType>
struct SqList{
	ElemType *elem;
	int length;
	int listsize;
};

template <class ElemType>
class List {
	public:
		List();
		~List();

		int InitList_Sq();
		int DestroyList_Sq();
		//void ClearList_Sq() const;
		bool ListEmpty_Sq() const;
		int ListLength_Sq() const;
		int GetElem_Sq(int i, ElemType& e) const;
		int LocateElem_Sq(ElemType e) const;
		//int PriorElem_Sq(ElemType cur_e, ElemType &pre_e);
		int ListInsert_Sq(int i,ElemType &e);
		int ListDelete_Sq(int i,ElemType &e);
		int ListAddElem(ElemType e);
		int ListDelLast(ElemType& e);
		
		ElemType ListGetLast();
	private:
		SqList<ElemType> SeqList;
};

template <class ElemType>
ElemType List<ElemType>::ListGetLast()
{
	return SeqList.elem[SeqList.length-1];
}

template <class ElemType>
int List<ElemType>::ListAddElem(ElemType e)
{
	SeqList.elem[SeqList.length++]=e;
	return 0;
}

template <class ElemType>
int List<ElemType>::ListDelLast(ElemType& e)
{
	ListDelete_Sq(SeqList.length,e);
	return 0;
}


template <class ElemType>
List<ElemType>::List()
{
	InitList_Sq();
}

template<class ElemType>
List<ElemType>::~List()
{
	DestroyList_Sq();
}

template<class ElemType>
int List<ElemType>::InitList_Sq()
{
	SeqList.elem=new ElemType[LIST_INIT_SIZE];
	if(!SeqList.elem)
		exit(EXIT_FAILURE);
	SeqList.length=0;
	SeqList.listsize=LIST_INIT_SIZE;
	
	return 0;
}

template<class ElemType>
int List<ElemType>::DestroyList_Sq()
{
	delete[] (SeqList.elem);
}

template<class ElemType>
bool List<ElemType>::ListEmpty_Sq() const
{
	return SeqList.length==0;
}

template<class ElemType>
int List<ElemType>::ListLength_Sq() const
{
	return SeqList.length;
}

template<class ElemType>
int List<ElemType>::GetElem_Sq(int i,ElemType &e) const
{
	e=SeqList.elem[i-1];
	return 0;
}

template<class ElemType>
int List<ElemType>::LocateElem_Sq(const ElemType e) const
{
	for(int i=0;i<SeqList.listsize;++i)
	{
		if(SeqList.elem[i]==e)
			return i+1;
	}

	return -1;
}

template<class ElemType>
int List<ElemType>::ListInsert_Sq(int i,ElemType& e)
{
	if(i<1||i>ListLength_Sq())
		return -1;

	ElemType* p=&(SeqList.elem[i-1]);
	ElemType* q;
	for(q=&(SeqList.elem[SeqList.length-1]);q>=p;--q)
		*(q+1)=*q;

	*q=e;
	++SeqList.length;
	return 0;
}

template<class ElemType>
int List<ElemType>::ListDelete_Sq(int i,ElemType &e)
{
	if(i<1||i>SeqList.length)
		return -1;
	ElemType* p=&(SeqList.elem[i-1]);
	e = *p;
	ElemType* q=SeqList.elem+SeqList.length-1;
	for(++p;p<=q;++p)
		*(p-1)=*p;
	--SeqList.length;
	
	return 0;
}

